//
// (C) Copyright 2009 Irantha Suwandarathna (irantha@gmail.com)
// All rights reserved.
//

/* Copyright (c) 2001-2008, The HSQL Development Group
 * All rights reserved.
 *
 * Redistribution and use _in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions _in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer _in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the HSQL Development Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


using System;
using EffiProz.Core;


namespace EffiProz.Core.Lib
{
    /**
     * Maintains an ordered  integer->integer lookup table, consisting of two
     * columns, one for keys, the other for values.
     *
     * The table is sorted on either the key or value column, depending on the calls to
     * setKeysSearchTarget() or setValuesSearchTarget(). By default, the table is
     * sorted on values.<p>
     *
     * findXXX() methods return the array index into the list
     * pair containing a matching key or value, or  or -1 if not found.<p>
     *
     * Sorting methods originally contributed by Tony Lai.
     *
     * @author fredt@users
     * @version 1.8.0
     * @since 1.8.0
     */
    public class DoubleIntIndex : IntLookup
    {

        private int count = 0;
        private int _capacity;
        private bool sorted = true;
        private bool sortOnValues = true;
          private bool fixedSize;
        private int[] keys;
        private int[] values;

        //
        private int targetSearchValue;

        public DoubleIntIndex(int capacity, bool fixedSize)
        {

            this._capacity = capacity;
            keys = new int[capacity];
            values = new int[capacity];
            this.fixedSize = fixedSize;
        }

        public int getKey(int i)
        {
            lock (this)
            {
                if (i < 0 || i >= count)
                {
                    throw new ArgumentOutOfRangeException();
                }

                return keys[i];
            }
        }

        public int getValue(int i)
        {
            lock (this)
            {
                if (i < 0 || i >= count)
                {
                    throw new ArgumentOutOfRangeException();
                }

                return values[i];
            }
        }

        /**
         * Modifies an existing pair.
         * @param i the index
         * @param key the key
         */
        public void setKey(int i, int key)
        {
            lock (this)
            {
                if (i < 0 || i >= count)
                {
                    throw new ArgumentOutOfRangeException();
                }

                if (!sortOnValues)
                {
                    sorted = false;
                }

                keys[i] = key;
            }
        }

        /**
         * Modifies an existing pair.
         * @param i the index
         * @param value the value
         */
        public void setValue(int i, int value)
        {
            lock (this)
            {
                if (i < 0 || i >= count)
                {
                    throw new ArgumentOutOfRangeException();
                }

                if (sortOnValues)
                {
                    sorted = false;
                }

                values[i] = value;
            }
        }

        public int size()
        {
            lock (this)
            {
                return count;
            }
        }

        public int capacity()
        {
            lock (this)
            {
                return _capacity;
            }
        }

        /**
         * Adds a pair into the table.
         *
         * @param key the key
         * @param value the value
         * @return true or false depending on success
         */
        public bool addUnsorted(int key, int value)
        {
            lock (this)
            {
                if (count == _capacity)
                {
                    if (fixedSize)
                    {
                        return false;
                    }
                    else
                    {
                        doubleCapacity();
                    }
                }

                if (sorted && count != 0)
                {
                    if (sortOnValues)
                    {
                        if (value < values[count - 1])
                        {
                            sorted = false;
                        }
                    }
                    else
                    {
                        if (value < keys[count - 1])
                        {
                            sorted = false;
                        }
                    }
                }

                keys[count] = key;
                values[count] = value;

                count++;

                return true;
            }
        }

        /**
         * Adds a key, value pair into the table with the guarantee that the key
         * is equal or larger than the largest existing key. This prevents a sort
         * from taking place on next call to find()
         *
         * @param key the key
         * @param value the value
         * @return true or false depending on success
         */
        public bool addSorted(int key, int value)
        {
            lock (this)
            {
                if (count == _capacity)
                {
                    if (fixedSize)
                    {
                        return false;
                    }
                    else
                    {
                        doubleCapacity();
                    }
                }

                if (count != 0 && value < values[count - 1])
                {
                    return false;
                }
        
                keys[count] = key;
                values[count] = value;

                count++;

                return true;
            }
        }

        /**
         * Adds a pair, ensuring no duplicate key xor value already exists _in the
         * current search target column.
         * @param key the key
         * @param value the value
         * @return true or false depending on success
         */
        public bool addUnique(int key, int value)
        {
            lock (this)
            {
                if (count == _capacity)
                {
                    if (fixedSize)
                    {
                        return false;
                    }
                    else
                    {
                        doubleCapacity();
                    }
                }

                if (!sorted)
                {
                    fastQuickSort();
                }

                targetSearchValue = sortOnValues ? value
                                                 : key;

                int i = binaryEmptySlotSearch();

                if (i == -1)
                {
                    return false;
                }


                if (count != i)
                {
                    moveRows(i, i + 1, count - i);
                }

                keys[i] = key;
                values[i] = value;

                count++;

                return true;
            }
        }

        /**
         * Adds a pair, maintaining sorted order
         * current search target column.
         * @param key the key
         * @param value the value
         * @return true or false depending on success
         */
        public bool add(int key, int value)
        {
            lock (this)
            {
                if (count == _capacity)
                {
                    if (fixedSize)
                    {
                        return false;
                    }
                    else
                    {
                        doubleCapacity();
                    }
                }

                if (!sorted)
                {
                    fastQuickSort();
                }

                targetSearchValue = sortOnValues ? value
                                                 : key;

                int i = binarySlotSearch();

                if (i == -1)
                {
                    return false;
                }


                if (count != i)
                {
                    moveRows(i, i + 1, count - i);
                }

                keys[i] = key;
                values[i] = value;

                count++;

                return true;
            }
        }

        public int lookupFirstEqual(int key)
        {

            if (sortOnValues)
            {
                sorted = false;
                sortOnValues = false;
            }

            int i = findFirstEqualKeyIndex(key);

            if (i == -1)
            {
                throw new InvalidOperationException();
            }

            return getValue(i);
        }

        public int lookupFirstGreaterEqual(int key)
        {

            if (sortOnValues)
            {
                sorted = false;
                sortOnValues = false;
            }

            int i = findFirstGreaterEqualKeyIndex(key);

            if (i == -1)
            {
                throw new InvalidOperationException();
            }

            return getValue(i);
        }

        public void setValuesSearchTarget()
        {
            lock (this)
            {
                if (!sortOnValues)
                {
                    sorted = false;
                }

                sortOnValues = true;
            }
        }

        public void setKeysSearchTarget()
        {
            lock (this)
            {
                if (sortOnValues)
                {
                    sorted = false;
                }

                sortOnValues = false;
            }
        }

        /**
         * @param value the value
         * @return the index
         */
        public int findFirstGreaterEqualKeyIndex(int value)
        {
            lock (this)
            {
                int index = findFirstGreaterEqualSlotIndex(value);

                return index == count ? -1
                                      : index;

            }
        }

        /**
         * @param value the value
         * @return the index
         */
        public int findFirstEqualKeyIndex(int value)
        {
            lock (this)
            {
                if (!sorted)
                {
                    fastQuickSort();
                }

                targetSearchValue = value;

                return binaryFirstSearch();
            }
        }

        /**
         * This method is similar to findFirstGreaterEqualKeyIndex(int) but
         * returns the index of the empty row past the end of the array if
         * the search value is larger than all the values / keys _in the searched
         * column.
         * @param value the value
         * @return the index
         */
        public int findFirstGreaterEqualSlotIndex(int value)
        {
            lock (this)
            {
                if (!sorted)
                {
                    fastQuickSort();
                }

                targetSearchValue = value;

                return binarySlotSearch();
            }
        }

        /**
         * Returns the index of the lowest element == the given search target,
         * or -1
         * @return index or -1 if not found
         */
        private int binaryFirstSearch()
        {

            int low = 0;
            int high = count;
            int mid = 0;
            int _compare = 0;
            int found = count;

            while (low < high)
            {
                mid = (low + high) / 2;
                _compare = compare(mid);

                if (_compare < 0)
                {
                    high = mid;
                }
                else if (_compare > 0)
                {
                    low = mid + 1;
                }
                else
                {
                    high = mid;
                    found = mid;
                }
            }

            return found == count ? -1
                                  : found;
        }

        /**
         * Returns the index of the lowest element > the given search target
         *     @return the index
         */
        private int binaryGreaterSearch()
        {

            int low = 0;
            int high = count;
            int mid = 0;
            int _compare = 0;

            while (low < high)
            {
                mid = (low + high) / 2;
                _compare = compare(mid);

                if (_compare < 0)
                {
                    high = mid;
                }
                else
                {
                    low = mid + 1;
                }
            }

            return low == count ? -1
                                : low;
        }

        /**
         * Returns the index of the lowest element >= the given search target,
         * or count
         *     @return the index
         */
        private int binarySlotSearch()
        {

            int low = 0;
            int high = count;
            int mid = 0;
            int _compare = 0;

            while (low < high)
            {
                mid = (low + high) / 2;
                _compare = compare(mid);

                if (_compare <= 0)
                {
                    high = mid;
                }
                else
                {
                    low = mid + 1;
                }
            }

            return low;
        }

        /**
         * Returns the index of the lowest element > the given search target
         * or count or -1 if target is found
         * @return the index
         */
        private int binaryEmptySlotSearch()
        {

            int low = 0;
            int high = count;
            int mid = 0;
            int _compare = 0;

            while (low < high)
            {
                mid = (low + high) / 2;
                _compare = compare(mid);

                if (_compare < 0)
                {
                    high = mid;
                }
                else if (_compare > 0)
                {
                    low = mid + 1;
                }
                else
                {
                    return -1;
                }
            }

            return low;
        }

        private void fastQuickSort()
        {
            lock (this)
            {
                quickSort(0, count - 1);
                insertionSort(0, count - 1);

                sorted = true;
            }
        }

        private void quickSort(int l, int r)
        {

            int M = 4;
            int i;
            int j;
            int v;

            if ((r - l) > M)
            {
                i = (r + l) / 2;

                if (lessThan(i, l))
                {
                    swap(l, i);    // Tri-Median Methode!
                }

                if (lessThan(r, l))
                {
                    swap(l, r);
                }

                if (lessThan(r, i))
                {
                    swap(i, r);
                }

                j = r - 1;

                swap(i, j);

                i = l;
                v = j;

                for (; ; )
                {
                    while (lessThan(++i, v)) { }

                    while (lessThan(v, --j)) { }

                    if (j < i)
                    {
                        break;
                    }

                    swap(i, j);
                }

                swap(i, r - 1);
                quickSort(l, j);
                quickSort(i + 1, r);
            }
        }

        private void insertionSort(int lo0, int hi0)
        {

            int i;
            int j;

            for (i = lo0 + 1; i <= hi0; i++)
            {
                j = i;

                while ((j > lo0) && lessThan(i, j - 1))
                {
                    j--;
                }

                if (i != j)
                {
                    moveAndInsertRow(i, j);
                }
            }
        }

        private void moveAndInsertRow(int i, int j)
        {

            int col1 = keys[i];
            int col2 = values[i];

            moveRows(j, j + 1, i - j);

            keys[j] = col1;
            values[j] = col2;
        }

        private void doubleCapacity()
        {
            Array.Resize<int>(ref keys, _capacity * 2);
            Array.Resize<int>(ref values, _capacity * 2);

            _capacity *= 2;
        }

        private void swap(int i1, int i2)
        {

            int col1 = keys[i1];
            int col2 = values[i1];

            keys[i1] = keys[i2];
            values[i1] = values[i2];
            keys[i2] = col1;
            values[i2] = col2;
        }

        private void moveRows(int fromIndex, int toIndex, int rows)
        {
            Array.Copy(keys, fromIndex, keys, toIndex, rows);
            Array.Copy(values, fromIndex, values, toIndex, rows);
        }

        public void removeRange(int start, int limit)
        {

            moveRows(limit, start, count - limit);

            count -= (limit - start);
        }

        public void removeAll()
        {

            Array.Clear( keys, 0, count);
            Array.Clear( values, 0, count);

            count = 0;
        }

        /**
         * Check if targeted column value _in the row indexed i is less than the
         * search target object.
         * @param i the index
         * @return -1, 0 or +1
         */
        private int compare(int i)
        {

            if (sortOnValues)
            {
                if (targetSearchValue > values[i])
                {
                    return 1;
                }
                else if (targetSearchValue < values[i])
                {
                    return -1;
                }
            }
            else
            {
                if (targetSearchValue > keys[i])
                {
                    return 1;
                }
                else if (targetSearchValue < keys[i])
                {
                    return -1;
                }
            }

            return 0;
        }

        public void remove(int position)
        {
            lock (this)
            {

                moveRows(position + 1, position, count - position - 1);

                count--;

                keys[count] = 0;
                values[count] = 0;
            }
        }

        /**
         * Check if row indexed i is less than row indexed j
         * @param i the first index
         * @param j the second index
         * @return true or false
         */
        private bool lessThan(int i, int j)
        {

            if (sortOnValues)
            {
                if (values[i] < values[j])
                {
                    return true;
                }
            }
            else
            {
                if (keys[i] < keys[j])
                {
                    return true;
                }
            }

            return false;
        }
    }
}
